package bfs;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class 为高尔夫比赛砍树 {
	public static int l,r,m,n,pos_i,pos_j;
    public static int MAXM=51;
    public static int MAXN=51;
    public static boolean[][] visit;
    public static int[] dx={1,-1,0,0};
    public static int[] dy={0,0,1,-1};
    public static int[][] queue=new int[MAXM*MAXN][2];
    
    //求两个点直接的最小路径，该方法你应该很熟悉；
    //起始点坐标为pos_i,pos_j,每次计算为最小路径后，将前一轮的终点赋为该坐标
    //终点target，这里未使用坐标，因为bfs一定会找到/找不到它，因此不需要传坐标也可以
    
    //该bfs也可以传坐标，起始坐标+终点坐标作为参数；
    public static int findMinWay(List<List<Integer>> forest,int target){
        if(target==forest.get(pos_i).get(pos_j)) return 0;
        l=r=0;
        visit=new boolean[MAXM][MAXN];
        queue[r][0]=pos_i;
        queue[r++][1]=pos_j;
        visit[pos_i][pos_j]=true;
        int step=0;
        while(l<r){
            int size=r-l;
            for(int i=0;i<size;i++){
                int nx=queue[l][0],ny=queue[l++][1];
                for(int k=0;k<4;k++){
                    int x=nx+dx[k],y=ny+dy[k];
                    //只要存在终点数target，就一定会走到该部分返回
                    if(x>=0&&x<m&&y>=0&&y<n&&visit[x][y]==false&&forest.get(x).get(y)>=1){
                        if(forest.get(x).get(y)==target){
                        	//更新起点
                            pos_i=x;
                            pos_j=y;
                            return step+1;
                        }
                        queue[r][0]=x;
                        queue[r++][1]=y;
                        visit[x][y]=true;           
                    }
                }
            }
            step++;
        }
        return -1;
    }
    public int cutOffTree(List<List<Integer>> forest) {
        pos_i=pos_j=0;
        m=forest.size();
        n=forest.get(0).size();
        Set<Integer> hash=new TreeSet<>();
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(forest.get(i).get(j)>1){
                    hash.add(forest.get(i).get(j));
                }
            }
        }

        List<Integer> arr=new ArrayList<>(hash);
        int ret=0;
      //各颗树依次作为终点，求最小路径
        for(int i=0;i<arr.size();i++){
            int res=findMinWay(forest,arr.get(i));
            //一但不存在最小路径，就直接返回
            if(res==-1){
                return -1;
            }
            ret+=res;
        }
        return ret;
    }
}
